/*
	file name:dichotomy.c
	file object:二分查找
	base:1.数据结构类型为数组
	2.元素升序排列或者降序
	3.数据中的元素不相同，否则可能会造成失误
	theory:首先将要查找的元素(key)与数组中的元素进行比较
	1. 如果key小于中间元素,只需要在数组的前一半元素中继续查找
	2. 如果key和中间元素相等，匹配成功，查找结束
	3. 如果key大于中间元素，只需要在数组的后一半元素中继续查找key。
	created time: 2022-03-22
*/

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<unistd.h>
#include<errno.h>
#include<pthread.h>


void sys_err(char* str){
	perror(str);
	exit(1);
}

int key_2(int* nums,int length,int target);	//通过两个关键值搜索

int main(int argc,char* argv[]){
	int n=0,i=0;	//存储数组元素个数
	int nums[10000];
	int target=0;
	printf("Please input the 1st number(input 'q' means finished):");
	for(i=0;scanf("%d",&nums[i])==1;i++){
		getchar();
		printf("\nPlease input the %dth number: ",i+2);
		n++;
	}
	getchar();
	printf("\nPlease input the target= ");
	scanf("%d",&target);
	printf("The result of key_1() is %d\n",key_2(nums,n,target));
	return 0;
}

int key_2(int* nums,int length,int target){
	int l=-1,r=length;
	int m=0;
	while((l+1) != r){
		m=(l+r)/2;
		if(*(nums+m) == target)
			l=m;
		else
			r=m;
	}
	return l;
}
